﻿using System;
using System.Collections.Generic;
//using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Grafo
{
    public class Grafo<T>
    {

        private int numVertices;
        private int numAristas;
        private List<T> vertices;
        private List<Arista<T>> aristas;
        private string _id;
        bool dirigido;

        /**
         *Construye un grafo dirigido
         * */
        public Grafo(bool dirigido,string id)
        {
            _id = id;
            numVertices = 0;
            numAristas = 0;
            aristas = new List<Arista<T>>();
            vertices = new List<T>();
            this.dirigido = dirigido;
            
        }

        /*
         * retorna todas las aristas como una lista con un arreglo de 
         * objetos (vertice inicio, vertice fin, peso).
         */
        public List<Object[]> darAristas()
        {
            List<Object[]> salida = new List<Object[]>();
            foreach (Arista<T> aristaT in aristas)
            {
                Object[] temporal = {aristaT.darInicio(),aristaT.darFin(),aristaT.darPeso()};
                salida.Add(temporal);
            }            
            return salida;
        }

        /*
         * retorna el id del grafo.
         */
        public string darId()
        {
            return _id;
        }

        /**
         *retorna el numero de vertices del grafo
         * */
        public int darNumVertices()
        {
            return numVertices;
        }

        /**
         *retorna el numero de aristas del grafo
         * */
        public int darNumAristas()
        {
            return numAristas;
        }

        /**
         *agrega un vertice
         *@param nombre es la etiqueta del vertice, es un string != null
         *pos: el arreglo de vertices tiene el nuevo vï¿½rtice en la posiciï¿½n numVertices, se inicializa la lista
         * de adyacencias (vacï¿½a) para el nuevo vï¿½rtice, se actualiza la cantidad de vï¿½rtices en el grafo.
         * */
        public void addVertice(T nombre)
        {            
            vertices.Add(nombre);
            numVertices++;
        }

        public double darPesoArista(T inicio,T fin){
            double salida = -1;
            for (int i = 0; i < aristas.Count(); i++)
            {
                Arista<T> a = aristas.ElementAt(i);
                if (a.darInicio().Equals(inicio) && a.darFin().Equals(fin))
                {
                   salida = a.darPeso();
                }
            }
            return salida;
        }

        /**
         *agrega una arista
         *@param i y f son las etiquetas de los  vertices de inicio y fin de la arista respectivamente, y y f son
         *strings != null, w es un entero
         *pos: se agrega a la lista de adyacencias del vertice de origen la nueva arista.
         *Se verifica que los vertices de la entrada esten en el conjunto de vertices y que no exista la arista
         * */
        public bool addArista(T inicio, T fin, double w)
        {
            bool agrego = false;
            if (dirigido)
            {
                bool existe = buscarArista(inicio, fin);
                if (!existe)
                {
                    aristas.Add(new Arista<T>(inicio, fin, w));
                    agrego = true;
                    numAristas++;
                }
            }
            else
            {
                bool existe = buscarArista(inicio, fin);
                if (!existe)
                {
                    aristas.Add(new Arista<T>(inicio, fin, w));
                    numAristas++;
                    aristas.Add(new Arista<T>(fin, inicio, w));
                    numAristas++;
                    agrego = true;
                }
            }
            return agrego;
        }

        private T buscarVertice(int index)
        {
            return vertices.ElementAt(index);
        }
        
        public bool buscarArista(T inicio, T fin)
        {
            bool esta = false;
            for (int i = 0; i < aristas.Count(); i++)
            {
                Arista<T> a = aristas.ElementAt(i);
                if (a.darInicio().Equals(inicio) && a.darFin().Equals(fin))
                {
                    esta = true;
                }
            }
            return esta;
        }

        public String printVertices()
        {
            String salida = "";
            for (int i = 0; i < numVertices; i++)
            {
                salida += vertices.ElementAt(i) + " ";
            }
            return salida;
        }

        public Boolean encontarVertice(T vertice)
        {
            Boolean resultado = false;
            for (int i = 0; i < numVertices && !resultado; i++)
            {
                if (vertices.ElementAt(i).Equals(vertice))
                {
                    resultado = true;
                }
            }
            return resultado;
        }

        public List<Arista<T>> darAristas(T vertice)
        {
            List<Arista<T>> aristas = new List<Arista<T>>();           

            for (int i = 0; i < numAristas; i++)
            {
                Arista<T> arista = this.aristas.ElementAt(i);
                if (arista.darInicio().Equals(vertice))
                    aristas.Add(arista);
            }
            return aristas;
        }

        public String printAristas()
        {
            List<Arista<T>> salida = aristas;
            String cadena = "";
            for (int i = 0; i < salida.Count(); i++)
            {
                cadena += salida.ElementAt(i).toString() + " ";
            }
            return cadena;
        }

        public List<T> darVertices()
        {
            return vertices;
        }

        public int darPosVertice(T vertice)
        {
            for (int i = 0; i < vertices.Count(); i++)
            {
                if (vertice.Equals(vertices.ElementAt(i)))
                    return i;
            }
            return -1;
        }

        public void profundidad(Grafo<T> g, T vertice, bool[] visitados, List<T> lista)
        {
            int i = darPosVertice(vertice);
            visitados[i] = true;
            lista.Add(vertices.ElementAt(i));
            for (int j = 0; j < g.numVertices; j++)
            {
                if ((i != j) && (!visitados[j]) && (g.buscarArista(vertice, vertices.ElementAt(j))))
                    profundidad(g, vertices.ElementAt(j), visitados, lista);
            }
        }

        public List<T> profundidad()
        {
            bool[] visitados = new bool[numVertices];
            List<T> lista = new List<T>();
            for (int i = 0; i < numVertices; i++)
            {
                if (!visitados[i])
                    profundidad(this, vertices.ElementAt(i), visitados, lista);
                return lista;
            }
            return lista;
        }

        public void amplitud(List<T> lista)
        {
            Queue<T> cola = new Queue<T>();
            bool[] visitados = new bool[numVertices];
            T vertice = vertices.ElementAt(0);
            for (int i = 0; i < numVertices; i++)
            {
                if (!visitados[i])
                {
                    cola.Enqueue(vertice);
                    visitados[i] = true;
                }
                while (cola.Count>0)
                {
                    vertice = cola.Peek();
                    cola.Dequeue();
                    lista.Add(vertice);
                    List<Arista<T>> aristas = darAristas(vertice);
                    for (int j = 0; j < aristas.Count(); j++)
                    {
                        int pos = darPosVertice(aristas.ElementAt(j).darFin());
                        if (!visitados[pos])
                        {
                            cola.Enqueue(aristas.ElementAt(j).darFin());
                            visitados[pos] = true;
                        }
                    }
                }
            }
        }

        public List<T> amplitud()
        {
            List<T> lista = new List<T>();
            amplitud(lista);
            return lista;
        }

        public Arista<T> aristaConInicio(T inicio)
        {
            for (int i = 0; i < aristas.Count(); i++)
            {
                if (aristas.ElementAt(i).darInicio().Equals(inicio))
                    return aristas.ElementAt(i);
            }
            return null;
        }
                     
    }
}
